#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

using std::vector;

void print_vec(std::vector<int> v) {
    for (auto value : v) {
        std::cout << value << ", ";
    }
    std::cout << std::endl;
}

class Solution {
  public:
    int lengthOfLIS(vector<int> &nums) {
        std::vector<std::vector<int>> best_v; // 目前最优的长度各异的序列
        best_v.push_back({INT_MIN});
        for (auto n : nums) {
            if (n > best_v.back().back()) {
                std::vector<int> tmp(best_v.back());
                tmp.push_back(n);
                best_v.push_back(tmp);
            }
            for (int i = best_v.size() - 2; i >= 0; --i) {
                if (n > best_v[i].back() and n < best_v[i + 1].back()) {
                    std::copy(best_v[i].begin(), best_v[i].end(),
                              best_v[i + 1].begin());
                    best_v[i + 1].back() = n;
                }
            }
        }
        return best_v.back().size() - 1;
    }

    int lengthOfLIS_dp(vector<int> &nums);
};

int Solution::lengthOfLIS_dp(vector<int> &nums){

}

int main() {
    std::vector<int> nums{1, 2, 3, 4, 111, 222, 333, 5, 6, 7, 8, 9, 0};
    Solution s;
    std::cout << s.lengthOfLIS(nums) << std::endl;
    return 0;
}